package com.daydayup.homework;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class GetAllSubset {

	/** 和，通过构造方法传入 */
	private int TARGET_SUM;
	public static List<String> printList = new ArrayList<String>();

	private Stack<String> stack = new Stack<String>();

	public GetAllSubset(int sum) {
		TARGET_SUM = sum;
	}

	private int sumInStack = 0;

	/**
	 * 计算主方法
	 * 
	 * @param list
	 * @param fromIndex
	 * @param endIndex
	 */
	public void populateSubset(final List<Map<String, Integer>> list, int fromIndex, int endIndex) {

		// 如果sumInStack和是需要的和，则打印栈中数据
		if (sumInStack >= TARGET_SUM) {
			if (sumInStack == TARGET_SUM) {
				print(stack);
			}
			return;
		}
		// 递归遍历，压栈，求和，递归结束弹栈进入下一次循环压栈递归
		for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
			Map<String, Integer> multiplys = list.get(currentIndex);
			for (String multiply : multiplys.keySet()) {
				stack.push(multiply);
				sumInStack += multiplys.get(multiply);
				populateSubset(list, currentIndex + 1, endIndex);
				sumInStack -= multiplys.get((String) stack.pop());
			}
		}
	}

	/**
	 * 递归打印栈中数据，如果是0怎排除，如果已经打印过则不再打印
	 * 
	 * @param stack
	 */
	private void print(Stack<String> stack) {
		StringBuilder sb = new StringBuilder();
		sb.append(TARGET_SUM).append(" = ");
		for (String i : stack) {
			if (i.indexOf("0") == -1) {
				sb.append(i).append("+");
			}
		}
		if (!printList.contains(sb.toString())) {
			printList.add(sb.toString());
			System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
		}
	}
}